MODULE sorting
  !-----------------------------------------------------------
  ! KRUUNUNHAKA basis set tool kit - sorting utilities
  !-----------------------------------------------------------
  ! See CHANGELOG
  !-----------------------------------------------------------
  ! Copyright (C) 2003-2008 Pekka Manninen, 2010 Jussi Lehtola
  !
  ! This program is distributed under the terms of the GNU General
  ! Public License as published by the Free Software Foundation;
  ! either version 2 of the License, or (at your option) any later version.
  !
  ! This program is distributed in the hope that it will be useful,
  ! but WITHOUT ANY WARRANTY; without even the implied warranty of
  ! MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
  !
  ! Please note that this program as well as its 
  ! author must be properly cited whenever the program or some parts 
  ! originated on it are employed. 
  !
  !-----------------------------------------------------------

  USE definitions
  IMPLICIT NONE
CONTAINS
!-----------------------------------------------------------
  ! Sort in descending order
  SUBROUTINE sort_desc(table)
    IMPLICIT NONE
    REAL(KIND=prec), INTENT(INOUT), DIMENSION(:) :: table
    REAL(KIND=prec) :: help
    INTEGER :: n, i, j
    
    n = SIZE(table)
    DO i = 2, n
       help = table(i)
       DO j = i, 2, -1
          IF(table(j-1) >= help) EXIT
          table(j) = table(j-1)
       END DO
       table(j) = help
    END DO
  END SUBROUTINE sort_desc
!-----------------------------------------------------------
  ! Sort in ascending order
  SUBROUTINE sort_asc(table)
    IMPLICIT NONE
    REAL(KIND=prec), INTENT(INOUT), DIMENSION(:) :: table
    REAL(KIND=prec) :: help
    INTEGER :: n, i, j
    
    n = SIZE(table)
    DO i = 2, n
       help = table(i)
       DO j = i, 2, -1
          IF(table(j-1) <= help) EXIT
          table(j) = table(j-1)
       END DO
       table(j) = help
    END DO
  END SUBROUTINE sort_asc
!-----------------------------------------------------------
  ! Get descending order of elements
  SUBROUTINE sort_order(table, order)
    IMPLICIT NONE
    REAL(KIND=prec), INTENT(IN), DIMENSION(:) :: table
    INTEGER, INTENT(OUT), DIMENSION(:) :: order
    ! Helper to do ordering
    INTEGER :: help
    INTEGER :: n, i, j

    n = SIZE(table)
    DO i=1,n
       order(i)=i
    END DO

    DO i = 2, n
       help = order(i)
       DO j = i, 2, -1
          IF(table(order(j-1)) >= table(help)) EXIT
          order(j) = order(j-1)
       END DO
       order(j) = help
    END DO
  END SUBROUTINE sort_order

END MODULE sorting
